#ifndef _contest_union_find_h_
#define _contest_union_find_h_

#include<vector>
#include<stdint.h>
#include<assert.h>

using namespace std;

namespace contest
{
class union_find
{
private:
    vector<int32_t> dad;
    vector<int32_t> rank;
public:
    union_find(const size_t size):
        dad(size, -1),
        rank(size, 0)
    {
    }
    bool merge(const size_t x, 
               const size_t y)
    {
        int32_t i, j;
        for (i=x; dad[i]>=0; i=dad[i]);
        for (j=y; dad[j]>=0; j=dad[j]);
        if (i != j) {
            if (rank[i] < rank[j])
                dad[i] = j;
            else if (rank[i] > rank[j])
                dad[j] = i;
            else {
                 dad[j] = i;
                 rank[i]= rank[i] + 1;  
            }
        }
        return (i!=j);
    }
};
void test_union_find()
{
}
}

#endif
